package compiler.parser;

import compiler.grammar.NonTerminal;
import compiler.grammar.Production;
import compiler.grammar.Symbol;
import compiler.parser.lalr.LALRItem;
import compiler.parser.lalr.LALRState;
import compiler.parser.lalr.LALRTransition;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

public class LALREngine
{
    //~ Instance fields --------------------------------------------------------

    private final Map<Set<LALRItem>, LALRState> allStatesByKernel = new HashMap<Set<LALRItem>, LALRState>();
    private final Map<String, Symbol>           symbols;
    private Production                          startProduction;

    //~ Constructors -----------------------------------------------------------

    public LALREngine(Map<String, Symbol> symbols, Production startProduction) throws Exception
    {
        this.symbols = symbols;

        if (startProduction == null)
        {
            throw new Exception("Start Production = null");
        }

        this.startProduction = startProduction;
        this.generateMachine();
    }

    //~ Methods ----------------------------------------------------------------

    public Production getStartProduction()
    {
        return startProduction;
    }

    public Collection<LALRState> getStates()
    {
        return allStatesByKernel.values();
    }

    public Map<String, Symbol> getSymbols()
    {
        return symbols;
    }

    private LALRState expandAllNonTerminals(Set<LALRItem> kernel) throws Exception
    {
        Set<LALRItem> itemSet = new HashSet<LALRItem>();
        itemSet.addAll(kernel);

        Stack<LALRItem> test = new Stack<LALRItem>();
        test.addAll(itemSet);

        while (test.size() > 0)
        {
            LALRItem currItem = test.pop();

            if (currItem.getSymbolAfterDot() instanceof NonTerminal)
            {
                NonTerminal nonTerminalToadd = (NonTerminal)currItem.getSymbolAfterDot();

                for (Production prod : nonTerminalToadd.getProductions())
                {
                    LALRItem lalrItm = new LALRItem(prod, 0, currItem.computeFollowSet(currItem.getLookAhead()));

                    if (!itemSet.contains(lalrItm)) // in dupicate items merge lookahead (contains doesn't compare lookahead )
                    {
                        test.push(lalrItm); // add this item to test
                        itemSet.add(lalrItm);

                        currItem.addItemToPropagateTo(lalrItm);
                    }
                    else
                    {
                        /*
                        example where this happens
                         *  <a> =     <a> [b]
                         *          | [b] <c>
                         *          |
                         *          ;
                         *
                         *  <c> = [b] <a> ;
                         */
                        for (LALRItem it : itemSet)
                        {
                            if (it.equals(lalrItm))
                            {
                                //it.lookAhead.addAll(lalrItm.lookAhead);
                                it.propagateLookahead(lalrItm.getLookAhead()); // addAll is called implicitly there too

                                break;
                            }
                        }
                    }
                }
            }
        }

        LALRState state = new LALRState(true); // LARLState from all the items

        // this block effectivly sets the items to itemSet and kernel to kernel
        // i do that cuz the kernel is the unexpanded set of items. while i am setting the items to
        // the fully expanded set.
        for (LALRItem item : itemSet)
        {
            state.addLALRItem(item);
        }

        state.getKernel().clear();
        state.getKernel().addAll(kernel);

        state.setSealed();
        allStatesByKernel.put(kernel, state);

        return state;
    }

    private void generateMachine() throws Exception
    {
        LALRItem      item = new LALRItem(startProduction);

        Set<LALRItem> currentKernel = new HashSet<LALRItem>();

        currentKernel.add(item);

        LALRState        state = expandAllNonTerminals(currentKernel); // does the closure too

        // LALRState.AllStatesByKernel
        Stack<LALRState> statesToTest = new Stack<LALRState>();
        statesToTest.addAll(generateTransitions(state));

        while (statesToTest.size() > 0)
        {
            LALRState      currState = statesToTest.pop();

            Set<LALRState> newStateSet = generateTransitions(currState);

            for (LALRState st : newStateSet)
            {
                statesToTest.push(st);
            }
        }
    }

    private Set<LALRState> generateTransitions(LALRState stateFrom) throws Exception
    {
        /*
         * for all items in that state if dot is not at end shift, calc
         * followset if the shifted token is Nonterminal, else use the item's
         * lookahead, add the new item to a tempState indexed by the symbol end
         * for
         *
         * for all states if it doesn't already exists add it add all it's items
         * to the propagate items of the original items else add the lookaheads,
         * item by item. all all it's items to the propagate items of the
         * original items end for
         *
         * add the transitions
         */
        Map<Symbol, LALRState> tempStates = new HashMap<Symbol, LALRState>();

        Set<LALRState>         newStates = new HashSet<LALRState>();

        // #region part1
        for (LALRItem item : stateFrom.getItems())
        {
            if (!item.isDotAtEnd())
            {
                // i should only compute the follow set when expanding a non terminal, not when i am shifting on it !
                LALRItem newItm = item.Shift();

                newItm.setTempOriginItem(item);

                if (tempStates.containsKey(item.getSymbolAfterDot()))
                {
                    (tempStates.get(item.getSymbolAfterDot())).addLALRItem(newItm);
                }
                else
                {
                    LALRState tempState = new LALRState(false);
                    tempState.addLALRItem(newItm);
                    tempStates.put(item.getSymbolAfterDot(), tempState);
                }
            }
        }

        // #endregion
        for (Map.Entry<Symbol, LALRState> entry : tempStates.entrySet())
        {
            Symbol    transOn = entry.getKey();
            LALRState state = entry.getValue();

            LALRState stateTo = null;

            if (!allStatesByKernel.containsKey(state.getKernel()))
            {
                for (LALRItem i : state.getKernel())
                {
                    i.getTempOriginItem().addItemToPropagateTo(i);
                    i.setTempOriginItem(null);
                }

                LALRState newState = expandAllNonTerminals(state.getKernel());
                newStates.add(newState);
                stateTo = newState;
            }
            else
            {
                LALRState existingState = allStatesByKernel.get(state.getKernel());

                for (LALRItem tempItem : state.getKernel())
                {
                    for (LALRItem existingItem : existingState.getKernel())
                    {
                        if (tempItem.equals(existingItem))
                        {
                            // existingItem.LookAhead =
                            // existingItem.LookAhead.Union(tempItem.LookAhead);
                            existingItem.propagateLookahead(tempItem.getLookAhead());
                            tempItem.getTempOriginItem().addItemToPropagateTo(existingItem);
                        }
                    }
                }

                stateTo = existingState;
            }

            stateFrom.getTransitions().add(new LALRTransition(transOn, stateTo));
        }

        return newStates;
    }
}
